package stack.easy.单调栈题目汇总;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;

/**
 * 1. 问题描述
 *      给定两个 没有重复元素 的数组nums1 和nums2，其中nums1是nums2的子集。
 *      找到nums1中每个元素在nums2中的下一个比其大的值。
 *      nums1中数字x的下一个更大元素是指x在nums2中对应位置的右边的第一个比x大的元素。
 *      如果不存在，对应位置输出 -1 。
 *
 * 2， 算法分析
 *     分析为什么可以使用单调栈求解?
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 面试题下一个更大元素1 {
    public static void main(String[] args) {
        int[] ans = {1,2,3};
    }
    /**
     * 使用单调栈求出第二个数组的每个数字的右边第一个比当前元素大的数字
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        Deque<Integer> stack = new ArrayDeque<>(); // 创建栈
        HashMap<Integer,Integer> map = new HashMap<>();
        //  利用单调栈求出数组2中每个元素的右边第一个比它大的数字的值
        for(int i = 0; i < nums2.length; i++) {
            // 维护栈顶元素，当前入栈元素的永远都比栈顶元素小或者等于
            while(!stack.isEmpty() && stack.peek() < nums2[i]) {
                map.put(stack.pop(),nums2[i]);
            }
            stack.push(nums2[i]);
        }
        for(int num2 : nums2) {
            if(!map.containsKey(num2)) {
                map.put(num2,-1);
            }
        }
        int[] ans = new int[nums1.length];
        for(int i = 0; i < nums1.length; i++) {
            ans[i] = map.get(nums1[i]);
        }
        return ans;
    }
}
